package 中等.贪心思想;

import java.util.Arrays;

/**
 * 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。
 * 你的任务是从范围 [0, n - 1] 内找出  2 个满足下述所有条件的下标 i 和 j ：
 * abs(i - j) >= indexDifference 且
 * abs(nums[i] - nums[j]) >= valueDifference
 * 返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。
 * 如果存在多组可供选择的下标对，只需要返回其中任意一组即可。
 * 注意：i 和 j 可能 相等 。
 *
 * @ https://leetcode.cn/problems/find-indices-with-index-and-value-difference-ii/description/
 * @date 2024/08/06
 */
public class 找出满足差值条件的下标II_2905 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(findIndices(new int[]{22, 28, 50, 25}, 0, 28)));

    }

    /**
     * 贪心+预处理
     * 对应某个下班 i ，它只能找 [i+indexDifference,end] 范围内的数字
     * abs(nums[i] - nums[j]) >= valueDifference，要求绝对值 >= valueDifference
     * 那么需要找到 [i+indexDifference,end] 范围的最大值和最小值，如果他们不能满足
     * 条件，那么其他数字一样不能满足条件
     */
    public static int[] findIndices(int[] nums, int indexDifference, int valueDifference) {

        int[] rightMax = new int[nums.length];
        int[] rightMin = new int[nums.length];

        rightMax[nums.length - 1] = nums.length - 1;
        rightMin[nums.length - 1] = nums.length - 1;

        for (int i = nums.length - 2; i >= 0; i--) {

            rightMax[i] = rightMax[i + 1];
            if (nums[i] > nums[rightMax[i + 1]]) {
                rightMax[i] = i;
            }
            rightMin[i] = rightMin[i + 1];
            if (nums[i] < nums[rightMin[i + 1]]) {
                rightMin[i] = i;
            }
        }

        for (int i = indexDifference; i < nums.length; i++) {
            if (Math.abs(nums[rightMax[i]] - nums[i - indexDifference]) >= valueDifference) {
                return new int[]{i - indexDifference, rightMax[i]};
            }
            if (Math.abs(nums[rightMin[i]] - nums[i - indexDifference]) >= valueDifference) {
                return new int[]{i - indexDifference, rightMin[i]};
            }
        }

        return new int[]{-1, -1};
    }

}
